/**
 * 给定一个单链表L的头结点head,单链表L表示为:
 * L0->L1->...->Ln-1->Ln
 * 请将其重新排列后变为:
 * L0->Ln->L1->Ln-1->...
 * 示例1:
 *  输入: head = [1, 2, 3, 4]
 *  输出: [1, 4, 2, 3]
 * 示例2:
 *  输入: head = [1, 2, 3, 4, 5]
 *  输出: [1, 5, 2, 4, 3]
*/

function Node (data) {
    this.data = data;
    this.next = null;
}

const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);
const node5 = new Node(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;


function reorderList (head) {
    if (!head) return null;
    if (!head.next) return head;
    const arr = [];
    let p = head;
    while (p) {
        arr.push(p);
        const temp = p.next;
        p.next = null;
        p = temp;
    }
    const mid = Math.ceil(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    let leftIndex = 0;
    let rightIndex = right.length - 1;
    const temp = [];
    while(leftIndex < mid) {
        if (left[leftIndex]) temp.push(left[leftIndex]);
        if (right[rightIndex]) temp.push(right[rightIndex]);
        leftIndex++;
        rightIndex--;
    }
    for (let i = 0; i < temp.length; i++) {
        if (temp[i + 1]) {
            temp[i].next = temp[i + 1];
        } else {
            temp[i].next = null;
        }
    }
    return temp[0];
}

console.log(reorderList(node1));
